
import com.sun.org.apache.regexp.internal.RE;
import sun.reflect.generics.tree.Tree;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class BinaryTree {
        static class TreeNode {
            public int val;
            public TreeNode left;
            public TreeNode right;

            public TreeNode(int val) {
                this.val = val;
            }
        }

        private TreeNode root;
        public TreeNode createTree() {
            TreeNode A = new TreeNode('A');
            TreeNode B = new TreeNode('B');
            TreeNode C = new TreeNode('C');
            TreeNode D = new TreeNode('D');
            TreeNode E = new TreeNode('E');
            TreeNode F = new TreeNode('F');
            TreeNode G = new TreeNode('G');
            TreeNode H = new TreeNode('H');
            A.left = B;
            A.right = C;
            B.left = D;
            B.right = E;
            C.left = F;
            C.right = G;
            E.right = H;
            return A;
        }

        public void preOrder(TreeNode root){
            if(root==null) return;
            System.out.print(root.val+" ");
            preOrder(root.left);
            preOrder(root.right);
        }
        // 中序遍历
        public void inOrder(TreeNode root) {
            if (root == null) {
                return;
            }
            inOrder(root.left);
            System.out.print(root.val + " ");
            inOrder(root.right);
        }

        // 后序遍历
        public void postOrder(TreeNode root) {
            if (root == null) {
                return;
            }
            postOrder(root.left);
            postOrder(root.right);
            System.out.print(root.val + " ");
        }

        public List<TreeNode> preOrder2(TreeNode root){
            List<TreeNode> list=new ArrayList<>();
            if(root==null) return list;
            list.add(root);

            List<TreeNode> leftTree=preOrder2(root.left);
            list.addAll(leftTree);

            List<TreeNode> rightTree=preOrder2(root.right);
            list.addAll(rightTree);

            return list;

        }
    public List<TreeNode> inOrder2(TreeNode root){
        List<TreeNode> list=new ArrayList<>();
        if(root==null) return list;

        List<TreeNode> leftTree=inOrder2(root.left);
        list.addAll(leftTree);

        list.add(root);

        List<TreeNode> rightTree=inOrder2(root.right);
        list.addAll(rightTree);
        return list;

    }
    public List<TreeNode> postOrder2(TreeNode root){
        List<TreeNode> list=new ArrayList<>();
        if(root==null) return list;

        List<TreeNode> leftTree=postOrder2(root.left);
        list.addAll(leftTree);

        List<TreeNode> rightTree=postOrder2(root.right);
        list.addAll(rightTree);

        list.add(root);
        return list;

    }

    // 获取树中节点的个数

    //以 前/中/后序 遍历这棵树的时候，会把每个节点都遍历到。遍历一个节点就计数一次
    //较笨拙的方法——遍历的思想
    public void size1(TreeNode root) {
        if (root == null) {
            return;
        }
        int size=0;
        size++;
        size1(root.left);
        size1(root.right);
    }
    //改进
    public int size2(TreeNode root) {
        if (root == null) {
            return 0;
        } else {
            return 1 + size2(root.left) + size2(root.right);
        }
    }



    // 获取叶子节点的个数
    //遍历的思想
    public void getLeafNodeCount1(TreeNode root) {
            int leafsize=0;
        if (root == null) {
            return ;
        }

        if (root.left == null && root.right == null) {
            leafsize++;
        }

        getLeafNodeCount1(root.left);
        getLeafNodeCount1(root.right);

    }

    //进阶  root左树的叶子+root右树的叶子=整棵树的叶子

    public int getLeafNodeCount2(TreeNode root) {
        if (root == null) {
            return 0;
        } else if (root.left == null && root.right == null) {
            return 1;
        } else {
            return getLeafNodeCount2(root.left) + getLeafNodeCount2(root.right);
        }
    }


    // 获取第K层节点的个数
    //root这棵树的第K层=root.left的第k-1层+root.right的第k-1层
    //以此类推直到k=1
    public int getKLevelNodeCount(TreeNode root, int k) {
        if (root == null || k < 1) {
            return 0;
        } else if (k == 1) {
            return 1;
        } else {
            return getKLevelNodeCount(root.left, k - 1) +
                    getKLevelNodeCount(root.right, k - 1);
        }
    }

    // 获取二叉树的高度
    public int getHeight(TreeNode root) {
        if (root == null) {
            return 0;
        } else {
            int leftHeight = getHeight(root.left);
            int rightHeight = getHeight(root.right);
            return Math.max(leftHeight, rightHeight) + 1;
        }
    }
    public int getHeight2(TreeNode root) {
        if (root == null) {
            return 0;
        } else {
            int leftHeight = getHeight(root.left);
            int rightHeight = getHeight(root.right);
            return leftHeight > rightHeight ? leftHeight+ 1 : rightHeight+1;
        }
    }


    // 检测值为value的元素是否存在
    public TreeNode find(TreeNode root, int val) {
        if (root == null || root.val == val) {
            return root;
        } else {
            TreeNode leftResult = find(root.left, val);
            TreeNode rightResult = find(root.right, val);
            if (leftResult != null) {
                return leftResult;
            } else {
                return rightResult;
            }
        }
    }

    // 层序遍历
    public void levelOrder(TreeNode root) {
        if (root == null) {
            return;
        }

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            System.out.print(node.val + " ");

            if (node.left != null) {
                queue.offer(node.left);
            }

            if (node.right != null) {
                queue.offer(node.right);
            }
        }
    }

    // 判断一棵树是不是完全二叉树
    public boolean isCompleteTree(TreeNode root) {
        if (root == null) {
            return true;
        }

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        boolean flag = false; // 标志位，用于判断是否遇到了非完全节点

        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();

            if (node.left != null) {
                if (flag) {
                    return false; // 遇到非完全节点后，如果还有子节点，则不是完全二叉树
                }
                queue.offer(node.left);
            } else {
                flag = true; // 遇到了非完全节点
            }

            if (node.right != null) {
                if (flag) {
                    return false; // 遇到非完全节点后，如果还有子节点，则不是完全二叉树
                }
                queue.offer(node.right);
            } else {
                flag = true; // 遇到了非完全节点
            }
        }

        return true;
    }

    public static void main(String[] args) {
        BinaryTree binaryTree = new BinaryTree();

        // 构造二叉树
        binaryTree.root = new TreeNode(1);
        binaryTree.root.left = new TreeNode(2);
        binaryTree.root.right = new TreeNode(3);
        binaryTree.root.left.left = new TreeNode(4);
        binaryTree.root.left.right = new TreeNode(5);
        binaryTree.root.right.left = new TreeNode(6);
        binaryTree.root.right.right = new TreeNode(7);

        // 测试各个操作
        System.out.println("树中节点的个数: " + binaryTree.size2(binaryTree.root));
        System.out.println("叶子节点的个数: " + binaryTree.getLeafNodeCount2(binaryTree.root));
        System.out.println("第3层节点的个数: " + binaryTree.getKLevelNodeCount(binaryTree.root, 3));
        System.out.println("二叉树的高度: " + binaryTree.getHeight(binaryTree.root));
        System.out.println("值为5的元素是否存在: " + (binaryTree.find(binaryTree.root, 5) != null));
        System.out.println("层序遍历: ");
        binaryTree.levelOrder(binaryTree.root);
        System.out.println("\n是否完全二叉树: " + binaryTree.isCompleteTree(binaryTree.root));
    }
}